class Solution
{
public:
    vector<string> shortestSubstrings(vector<string> &arr)
    {
        vector<string> result;
        int n = arr.size();
        for (int i = 0; i < n; ++i)
        {
            string &s = arr[i];
            int len = s.size();
            bool allFound = false;
            for (int subLen = 1; subLen <= len; ++subLen)
            {
                string minSub(21, 'z');
                bool found = false;
                for (int j = 0; j + subLen <= len; ++j)
                {
                    string sub = s.substr(j, subLen);
                    bool notInOther = true;
                    for (int k = 0; k < n; ++k)
                    {
                        if (i == k)
                        {
                            continue;
                        }
                        if (arr[k].find(sub) != string::npos)
                        {
                            notInOther = false;
                            break;
                        }
                    }
                    if (notInOther)
                    {
                        found = true;
                        minSub = min(minSub, sub);
                    }
                }

                if (found)
                {
                    result.push_back(minSub);
                    allFound = true;
                    break;
                }
            }
            if (!allFound)
            {
                result.push_back("");
            }
        }
        return result;
    }
};